import problem.Problem

import scala.collection.mutable

class Q10RegularExpressionMatching extends Problem {

  def isMatch(s: String, p: String): Boolean = {
    val pattern = p.foldLeft(mutable.Buffer[(Char, Int)]()) { case (z, c) =>
      c match {
        case '*' => z.update(z.length - 1, (z.last._1, -1))
        case _ => z += ((c, 1))
      }
      z
    }.toArray
    if (s.length == 0 && p.length == 0) true
    else isMatch2(s.toCharArray, pattern)
  }

  def isMatch(a: Array[Char], pattern: Array[(Char, Int)]): Boolean = {
    if (pattern.isEmpty && a.isEmpty) true
    else if (a.isEmpty && pattern.nonEmpty) {
      if (pattern.forall(_._2 == -1)) true
      else false
    }
    else if (pattern.isEmpty && a.nonEmpty) false
    else {
      val (pc, count) = pattern.head
      if (pc == '.' || pc == a.head) {
        if (count == -1) {
          // 匹配上一个，继续匹配
          isMatch(a.tail, pattern) ||
            // 不匹配，跳过这个Pattern
            isMatch(a, pattern.tail) ||
            // 匹配，换下一个Pattern
            isMatch(a.tail, pattern.tail)
        } else isMatch(a.tail, pattern.tail)
      } else if (count == -1) isMatch(a, pattern.tail)
      else false
    }
  }

  def isMatch2(s: Array[Char], pattern: Array[(Char, Int)]): Boolean = {
    val dp: Array[Array[Int]] = Array.ofDim[Int](s.length, pattern.length)
    val v = f(s.length - 1, pattern.length - 1, None)(s, pattern, dp)
    // 打印，一眼就能看出哪里错了
    val sb = new StringBuilder("  ")
    val head = pattern.map { case (c, i) => if (i == 1) s" $c" else s"$c*" }.mkString(" ")
    sb.append(head + "\n")
    for (i <- s.indices) {
      sb.append(s"${s(i)} ")
      val line = dp(i).map(j => "%2d".format(j)).mkString(" ")
      sb.append(line + "\n")
    }
    println(sb.toString())
    v == 1
  }

  /**
   * dp(i)(j) 表示 match(s[:i], pattern[:j])
   * dp(i, j) = {dp(i-1, j), dp(i, j-1), dp(i-1, j-1)}
   */
  def f(i: Int, j: Int, m: Option[Char] = None)(implicit s: Array[Char], pattern: Array[(Char,
    Int)],
                                                dp: Array[Array[Int]])
  : Int = {
    if (j == -1) -1
    else if (i == -1) {
      if ((0 to j).forall(k => pattern(k)._2 == -1)) 1 else -1
    } else {
      if (dp(i)(j) != 0) dp(i)(j)
      else {
        val (c, occ) = pattern(j)
        // char匹配
        val p1 =
          if (m.isEmpty && charEquals(s(i), c) || m.nonEmpty && charEquals(s(i), m.get)) {
            if (i == 0 && j == 0) 1
            else if (occ == -1 && f(i - 1, j, Some(c)) == 1) 1
            else if (f(i - 1, j - 1, None) == 1) 1
            else -1
          } else -1

        // 模式不匹配，但是.*可以跳过
        val p2 =
          if (occ == -1) {
            if (m.nonEmpty) -1
            else f(i, j - 1, None)
          } else -1
        dp(i)(j) = math.max(p1, p2)
        dp(i)(j)
      }
    }
  }

  def charEquals(a: Char, p: Char): Boolean = {
    p == '.' || a == p
  }

  override def test(): Unit = {
    val cases = Table(("string", "pattern", "match"),
      ("", "", true),
      ("aa", "a", false),
      ("aa", "a*", true),
      ("ab", ".*", true),
      ("aab", "c*a*b", true),
      ("mississippi", "mis*is*p*.", false),
      ("mississippi", "mis*is*ip*.", true),
      ("a", "ab*", true),
      ("aaaccbccbcbaabcaa", "c*a*.*a*.*c*.c*.a*c", false),
      ("aasdfasdfasdfasdfas", "aasdf.*asdf.*asdf.*asdf.*s", true)
    )

    forAll(cases) { case (s, p, matched) =>
      isMatch(s, p) shouldBe matched
    }
  }
}
